ICPC Live Archive/4807 - Cocircular Points/4807.2.cpp

   1 // Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const double EPS = 1e-9;
  29 int cmp(double x, double y = 0, double tol = EPS) {
  30     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  31 }
  32
  33 struct point {
  34     double x, y;
  35     point(double x, double y) : x(x), y(y) {}
  36     point(){}
  37     bool operator < (const point &p) const {
  38         int t = cmp(this->x, p.x);
  39         if (t != 0) return t < 0;
  40         return cmp(this->y, p.y) < 0;
  41     }
  42     bool operator == (const point &p) const {
  43         return cmp(this->x, p.x) == 0 and cmp(this->y, p.y) == 0;
  44     }
  45 };
  46
  47 point center(const point &p, const point &q, const point &r) {
  48     double ax = q.x - p.x;
  49     double ay = q.y - p.y;
  50     double bx = r.x - p.x;
  51     double by = r.y - p.y;
  52     double d = ax*by - bx*ay;
  53
  54     if (cmp(d, 0) == 0) {
  55         printf("Points are collinear!\n");
  56         assert(false);
  57     }
  58
  59     double cx = (q.x + p.x) / 2;
  60     double cy = (q.y + p.y) / 2;
  61     double dx = (r.x + p.x) / 2;
  62     double dy = (r.y + p.y) / 2;
  63
  64     double t1 = bx*dx + by*dy;
  65     double t2 = ax*cx + ay*cy;
  66
  67     double x = (by*t2 - ay*t1) / d;
  68     double y = (ax*t1 - bx*t2) / d;
  69
  70     return point(x, y);
  71 }
  72
  73 point points[105];
  74 point centers[105];
  75
  76 int main(){
  77     int n;
  78     while (scanf("%d", &n) == 1) {
  79         if (n == 0) break;
  80
  81         for (int i = 0; i < n; ++i) {
  82             scanf("%lf %lf", &points[i].x, &points[i].y);
  83         }
  84
  85         if (n <= 2) {
  86             printf("%d\n", n);
  87             continue;
  88         }
  89
  90         int ans = 2;
  91         for (int i = 0; i < n; ++i) {
  92             for (int j = i + 1; j < n; ++j) {
  93                 int last = 0;
  94                 for (int k = 0; k < n; ++k) {
  95                     if (k == i or k == j) continue;
  96                     double x0 = points[i].x - points[k].x;
  97                     double y0 = points[i].y - points[k].y;
  98                     double x1 = points[j].x - points[k].x;
  99                     double y1 = points[j].y - points[k].y;
 100                     if ( cmp(x0*y1 - y0*x1, 0) == 0 ) continue; // collinear
 101                     centers[last++] = center(points[i], points[j], points[k]);
 102                 }
 103                 sort(centers, centers + last);
 104                 for (int k = 0; k < last; ) {
 105                     int same = k;
 106                     while (same < last and centers[k] == centers[same]) same++;
 107                     ans = max(ans, same - k + 2);
 108                     k = same;
 109                 }
 110             }
 111         }
 112         printf("%d\n", ans);
 113     }
 114     return 0;
 115 }